package com.leetcode.根据算法进行分类.前缀和相关;

/**
 * @author: ZhouBert
 * @date: 2021/3/1
 * @description: 303. 区域和检索 - 数组不可变
 * https://leetcode-cn.com/problems/range-sum-query-immutable/
 */
public class A_303_区域和检索_数组不可变 {

	public static void main(String[] args) {

	}

	/**
	 * 使用 数组缓存 的方式可以快速完成
	 * --
	 * 原本想用一个 hashMap 来存储每一次计算的值，结果发现只能通过算过的值达到 O(1) 的复杂度。
	 * 于是只能换个角度思考。
	 * 发现 storedArr - 以 0-i 的求和结果
	 * --
	 * 原来这就是经典的前缀和
	 */
	static class NumArray {

		/**
		 * 用于存储 storedArr[i]=sum(0-i)
		 */
		int[] storedArr;

		public NumArray(int[] nums) {
			if (nums == null || nums.length == 0) {
				return;
			}
			int len = nums.length;
			storedArr = new int[len];
			storedArr[0] = nums[0];
			for (int i = 1; i < len; i++) {
				storedArr[i] = storedArr[i - 1] + nums[i];
			}
		}

		public int sumRange(int i, int j) {
			if (storedArr == null) {
				return -1;
			}
			if (i == 0) {
				return storedArr[j];
			}
			return storedArr[j] - storedArr[i - 1];
		}
	}

}
